package Sort;

public class HeapSort {
    /**
     * 堆排序
     */
    public static void creatHeap(int[] arr){
        for (int parent = (arr.length-1-1)/2; parent >=0 ; parent--) {
            siftDown(arr,parent,arr.length);
        }
    }
    public static void siftDown(int[] arr,int parent,int size){
        int child=2*parent+1;
        while (child<size){
            if(child+1<size&&arr[child+1]>arr[child]){
                child++;
            }
            if(arr[child]>arr[parent]){
                swap(arr,parent,child);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    public static void swap(int[] arr,int i,int j){
        int tem=arr[i];
        arr[i]=arr[j];
        arr[j]=tem;
    }
    public static void heapSort(int[] arr){
        //先创建一个大根堆
        creatHeap(arr);
        int end=arr.length-1;
        while (end>0){
            swap(arr,0,end);
            siftDown(arr,0,end);
            end--;
        }

    }
    public static void main(String[] args) {
        int[] array={5,1,9,4,3};
        heapSort(array);
        for (int i = 0; i <array.length; i++) {
            System.out.print(array[i]+" ");
        }

    }
}
